/*
 * @lc app=leetcode.cn id=393 lang=typescript
 *
 * [393] UTF-8 编码验证
 */

// @lc code=start
function validUtf8(data: number[]): boolean {
  const MASK1 = 1 << 7;
  const MASK2 = MASK1 + (1 << 6);
  // 根据首字节高位1的数量返回编码长度
  const getBytes = (num: number): number => {
    // 1位编码
    if ((num & MASK1) === 0) return 1;
    let n = 0;
    let mask = MASK1;
    // 当高位是1的时候，继续循环
    while ((num & mask) !== 0) {
      n++;
      // 超过4位属于不合法的编码
      if (n > 4) return -1;
      mask >>= 1;
    }

    return n < 2 ? -1 : n;
  };
  // 验证其他字节是否合法（就是高位必须10开头）
  const isValid = (num: number): boolean => {
    return (num & MASK2) === MASK1;
  };

  const n = data.length;
  let idx = 0;
  while (idx < n) {
    const num = data[idx];
    const bytes = getBytes(num);
    // 编码长度不合法或者超出数组长度
    if (bytes < 0 || idx + bytes > n) return false;
    // 遍历bytes - 1个字节
    for (let i = 1; i < bytes; i++) {
      // 字节不合法
      if (!isValid(data[idx + i])) return false;
    }
    // 寻找下一个字节
    idx += bytes;
  }

  return true;
}
// @lc code=end
